A switching network typically is made of input ports and output ports that are interconnected by switches and wires, as described in, for example, U.S. Pat. No. 5,521,591 (incorporated by reference herein in its entirety). As described in column 1, lines 17-19 of U.S. Pat. No. 5,521,591, each wire in the network serves as a conduit for transmitting a message from one of its ends to the other of its ends. The term wire (or connection) includes any means for communicating data between switches, such as electrical wires, parallel groups of wires, optical fibers, multiplexed channels over single wires, or free space radio or optical communication paths. A switch (shown in FIG. 1 of U.S. Pat. No. 5,521,591 and attached hereto as FIG. 1) is an atomic unit that resembles a switching network in function (i.e., a switch has input ports 1A and 1B and output ports 1C and 1D, and connects the input ports to the output ports in any desired pattern).
A switching network may route any kind of digital or analog data including voice or video signals. In some networks, the routing is accomplished by setting of switches so that input ports become directly coupled to output ports (e.g., in a telephone network). In other networks, the inputs ports do not become directly coupled to the output ports. Instead, the messages are routed as packets through the network in steps. Typical examples of networks in which switching networks are used include telephone networks, data networks, computer networks, and interconnection networks in parallel data processing systems.
A butterfly network 2 (shown in FIG. 5 of U.S. Pat. No. 5,521,591 and attached hereto as FIG. 2) is a common example of a switching network. Network 2 is referred to as a butterfly network because the connections between nodes form a pattern resembling a butterfly. A butterfly network has the same number of inputs as it has outputs. The inputs are connected to the outputs via a set of switches organized into successive levels of switches. An N-input, N-output butterfly network has log2N+1 (hereinafter log2 will be referred to as 1 g) levels of switches, each level having N 2xc3x972 switches. Each switch 3 in the butterfly 2 has a distinct reference label  less than L,r greater than  where L is its level, and r is its row. In an N-input butterfly, the level L is an integer between 0 and 1 gN, and the row r is a 1 gN-bit binary number. The inputs and outputs reside on levels 0 and 1 gN, respectively. For L less than 1 gN, a switch labeled  less than L,r greater than  is connected to switches  less than L+1,r greater than  and  less than L+1,r(L) greater than  and, where r(L) denotes r with the Lth bit complemented.
U.S. Pat. No. 5,521,591 also teaches that xe2x80x9ca butterfly contains just one path from each input port to each output portxe2x80x9d (in column 8, lines 39-42), and suggests a xe2x80x9cmultibutterfly contains many paths from each input to each output portxe2x80x9d (column 8, lines 42-43). Regarding such a multibutterfly, U.S. Pat. No. 5,521,591 states (column 8, lines 43-46) xe2x80x9c[i]ndeed, there is still just one logical (up-down) path from any input to any output, but this logical path can be realized as any one of several physical paths.xe2x80x9d
In a butterfly network in accordance with the invention, a number of switches are set to provide two paths that are independent of each other (also called xe2x80x9cnode disjoint pathsxe2x80x9d), a first path from a first switch to a second switch, and a second path from the same first switch to a third switch. The switches to be set (from among a number of levels of switches in the butterfly network) are identified by performing a number of predetermined operations depending on locations of the first switch, the second switch and the third switch relative to one another.
Specifically, the to-be-set switches are identified by: starting with a switch at the end of a path (e.g. the first switch) as a preceding switch, changing a level number (e.g. incrementing the level number) of the preceding switch, and changing a bit of the row number of the preceding switch (e.g. replacing with a corresponding bit (or its inverse) from the row number of the other path end switch), thereby to identify a next switch in the path. The just-described two acts of changing are repeated, with the just-identified next switch as the preceding switch, until the other end of the path is reached. During the repetition, if a boundary of the butterfly network is reached (e.g. the last level is reached), direction of the path is reversed (e.g. by decrementing the level number), and the repetition is continued.
The two paths that are identified can be used to transfer information (also referred to as xe2x80x9ctrafficxe2x80x9d) through the butterfly network. In one embodiment, the two paths are used to redundantly route traffic from a source switch to a destination switch, for load balancing or for fault tolerance. Specifically, if, in addition to the just-described two paths, the second switch and the third switch are directly coupled (also referred to as xe2x80x9cconnectedxe2x80x9d) to one another in the butterfly network (with just a connection and no intervening switches), then the two paths and the connection form a xe2x80x9cring.xe2x80x9d Any two of the three switches in such a ring can be used as source and destination switches for routing the traffic through either or both paths in the ring. For example, initially a source switch is designated as the first switch, a destination switch is designated as the second switch, and any switch connected to the second switch is designated as the third switch. Thereafter, the two paths (from the first switch to the second and third switches) are identified, thereby to identify redundant routes between the source and destination switches.
If the second and third switches are not directly connected, but coupled through one or more switches (also called xe2x80x9cintervening switchesxe2x80x9d) in the butterfly network, then two paths and connections between the intervening switches form a ring that is used as described above. Irrespective of whether the second and third switches are coupled to each other, the same traffic can be multicast, from the first switch (source switch) over the first path and over the second path to each of the second switch and the third switch (both of which act as destination switches).